{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "联通笔试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "你是一个勇士，现在你准备去森林刷毛球怪，你有两个属性（血量，攻击力），毛球怪也有这两个属性。当你遭遇一只毛球怪时你们会进入战斗，然后你和毛球怪轮流攻击（你先手），每次使对方的血量减去自己攻击力的数值，当一方的血量小于等于0时死亡。现在你想知道在自己活看的前提下最多杀死几只毛球怪。\n",
    "输入描述\n",
    "第一行一个正整数t，代表测试数据组数。\n",
    "第二行四个正整数h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。\n",
    "所有整数大小不超过1000。\n",
    "输出描述\n",
    "共t行，每行一个整数x，代表最多能杀死多少毛球怪。如果能杀死无数只，输出-1。\n",
    "\n",
    "示例 1\n",
    "输入\n",
    "1\n",
    "5 1 2 1\n",
    "输出\n",
    "4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_kills(t, test_cases):\n",
    "    results = []\n",
    "    for case in test_cases:\n",
    "        h, a, H, A = case\n",
    "        if a >= H:\n",
    "            results.append(-1)\n",
    "            continue\n",
    "        if A == 0:\n",
    "            results.append(-1)\n",
    "            continue\n",
    "        kills = 0\n",
    "        while h > 0:\n",
    "            # 勇士攻击毛球怪\n",
    "            H -= a\n",
    "            if H <= 0:\n",
    "                kills += 1\n",
    "                H = case[2]  # 重置毛球怪的血量\n",
    "            else:\n",
    "                # 毛球怪反击\n",
    "                h -= A\n",
    "                if h <= 0:\n",
    "                    break\n",
    "        results.append(kills)\n",
    "    return results\n",
    "\n",
    "# 输入处理\n",
    "t = int(input())\n",
    "test_cases = []\n",
    "for _ in range(t):\n",
    "    h, a, H, A = map(int, input().split())\n",
    "    test_cases.append((h, a, H, A))\n",
    "\n",
    "# 计算结果\n",
    "results = max_kills(t, test_cases)\n",
    "\n",
    "# 输出结果\n",
    "for res in results:\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "请设计一个算法，给一个字符串进行二进制编码（哈夫曼编码），使得编码后字符串的长度最短。\n",
    "数据范围：字符串长度满足1＜n≤1000，本题有多组输入\n",
    "输入描述\n",
    "每组数据一行，为待编码的字符串。保证字符串长度小于等于1000。\n",
    "输出描述\n",
    "一行输出最短的编码后长度。\n",
    "示例1\n",
    "输入\n",
    "MT-TECH-TEAM\n",
    "输出\n",
    "33"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from collections import Counter\n",
    "import heapq\n",
    "import itertools\n",
    "\n",
    "class Node:\n",
    "    \"\"\"表示哈夫曼树的节点\"\"\"\n",
    "    def __init__(self, freq, char=None, left=None, right=None):\n",
    "        self.freq = freq\n",
    "        self.char = char\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "def calculate_huffman_length(s):\n",
    "    \"\"\"计算字符串的哈夫曼编码长度\"\"\"\n",
    "    # 统计字符频率\n",
    "    freq_counter = Counter(s)\n",
    "    \n",
    "    # 定义优先队列，元素为 (频率, 唯一计数器, 节点)\n",
    "    heap = []\n",
    "    count = itertools.count()\n",
    "    for char, freq in freq_counter.items():\n",
    "        node = Node(freq, char)\n",
    "        heapq.heappush(heap, (freq, next(count), node))\n",
    "    \n",
    "    # 构建哈夫曼树\n",
    "    while len(heap) > 1:\n",
    "        # 弹出频率最低的两个节点\n",
    "        freq1, _, left = heapq.heappop(heap)\n",
    "        freq2, _, right = heapq.heappop(heap)\n",
    "        new_freq = freq1 + freq2\n",
    "        # 创建新的内部节点\n",
    "        new_node = Node(new_freq, left=left, right=right)\n",
    "        # 将新节点推入堆中\n",
    "        heapq.heappush(heap, (new_freq, next(count), new_node))\n",
    "    \n",
    "    # 生成哈夫曼编码\n",
    "    huffman_codes = {}\n",
    "    def generate_codes(node, current_code):\n",
    "        if node is None:\n",
    "            return\n",
    "        if node.char is not None:\n",
    "            # 叶子节点，分配编码\n",
    "            huffman_codes[node.char] = current_code or \"\"\n",
    "            return\n",
    "        # 递归生成左右子树的编码\n",
    "        generate_codes(node.left, current_code + \"0\")\n",
    "        generate_codes(node.right, current_code + \"1\")\n",
    "    \n",
    "    if heap:\n",
    "        root = heap[0][2]\n",
    "        generate_codes(root, \"\")\n",
    "    \n",
    "    # 计算总编码长度\n",
    "    total_length = 0\n",
    "    for char, freq in freq_counter.items():\n",
    "        total_length += len(huffman_codes[char]) * freq\n",
    "    return total_length\n",
    "\n",
    "\n",
    "for line in sys.stdin:\n",
    "    s = line.strip()\n",
    "    if not s:\n",
    "        continue\n",
    "    length = calculate_huffman_length(s)\n",
    "    print(length)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给n个信封的长度和宽度。如果信封a的长和宽都小于信封b，那么信封a可以放到信封b里，请求出信封最多可以嵌套多少层。 \n",
    "数据范围：1≤n≤2×10^3，1≤letters[i][0],letters[i][1]≤2×10^3\n",
    "要求：空间复杂度 O（n），时间复杂度0（n^2）\n",
    "要求：空间复杂度 O（n），时间复杂度 O（nlogn） \n",
    "输入描述\n",
    "第一行输入一个正整数n，表示信封的数量\n",
    "后续 n 行每行输入两个正整数表示信封的长度和宽度 \n",
    "输出描述 输出最多可以嵌套的层数 \n",
    "\n",
    "示例1 \n",
    "输入 \n",
    "9 \n",
    "3 4 \n",
    "2 3\n",
    "4 5\n",
    "1 3\n",
    "2 2\n",
    "3 6\n",
    "1 2 \n",
    "3 2 \n",
    "2 4 \n",
    "输出 \n",
    "4 \n",
    "说明 从里到外是（1,2）（2,3）（3,4）（4,5）\n",
    "\n",
    "示例2\n",
    "输入\n",
    "2\n",
    "1 4\n",
    "4 1\n",
    "输出\n",
    "1\n",
    "\n",
    "Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_envelopes(n, envelopes):\n",
    "    # 先按长度升序排序，如果长度相同，按宽度降序排序\n",
    "    envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "    seq = []\n",
    "    for envelope in envelopes:\n",
    "        width = envelope[1]\n",
    "        left, right = 0, len(seq)\n",
    "        # 用二分查找找到第一个大于或等于width的位置\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if seq[mid] < width:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if left == len(seq):\n",
    "            seq.append(width)\n",
    "        else:\n",
    "            seq[left] = width\n",
    "    return len(seq)\n",
    "\n",
    "# 读取输入\n",
    "n = int(input())\n",
    "envelopes = [list(map(int, input().split())) for _ in range(n)]\n",
    "# 输出结果\n",
    "print(max_envelopes(n, envelopes))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二维数组map，含义是一张地图，例如，如下矩阵\n",
    "-2 -3 3\n",
    "-5 -10 1\n",
    "0 30 -5\n",
    "游戏的规则如下:\n",
    "1)骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。\n",
    "2)地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。\n",
    "3)骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?\n",
    "根据map,输出初始血量。\n",
    "输入描述\n",
    "第一行两个正整数n,m(1< n,m< 10^3),接下来n行，每行m个整数，代表mapij(-10^3< mapij < 10^3)。\n",
    "输出描述\n",
    "输出一个整数，表示答案，\n",
    "补充说明\n",
    "时间复杂度O(n*m),额外空间复杂度O(min(n,m))\n",
    "\n",
    "示例 1\n",
    "输入\n",
    "3 3\n",
    "-2 -3 3\n",
    "-5 -10 1\n",
    "0 30 -5\n",
    "输出\n",
    "7\n",
    "\n",
    "示例2\n",
    "输入\n",
    "2 2\n",
    "1 1\n",
    "1 1\n",
    "输出\n",
    "1\n",
    "\n",
    "Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_initial_health(n, m, map):\n",
    "    if n < m:\n",
    "        map = [list(x) for x in zip(*map)]\n",
    "        n, m = m, n\n",
    "    dp = [0] * m\n",
    "    dp[m-1] = max(1, 1 - map[n-1][m-1])\n",
    "    \n",
    "    for j in range(m-2, -1, -1):\n",
    "        dp[j] = max(1, dp[j+1] - map[n-1][j])\n",
    "    \n",
    "    for i in range(n-2, -1, -1):\n",
    "        dp[m-1] = max(1, dp[m-1] - map[i][m-1])\n",
    "        for j in range(m-2, -1, -1):\n",
    "            dp[j] = max(1, min(dp[j], dp[j+1]) - map[i][j])\n",
    "    \n",
    "    return dp[0]\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "map = [list(map(int, input().split())) for _ in range(n)]\n",
    "print(calculate_initial_health(n, m, map))\n",
    "# 给定一个二维数组map，含义是一张地图... →点击查看智谱清言智能体「深度推理」的回答https://chatglm.cn/share/F3W5J"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
